package com.example.demo.arithmetic.algorithm.dynamic_programing;

/**
 * 旅行商问题
 */
//TODO 复杂了一些
public class TravellingSalesmanProblem {
    public static void main(String[] args) {
        int[][] graph = {
                {0, 1, 2, 3},
                {1, 0, 6, 4},
                {2, 6, 0, 5},
                {3, 4, 5, 0}
        };

        System.out.println(tsp(graph));
    }


    private static int tsp(int[][] graph) {
        // 城市数目
        int m = graph.length;
        // 剩余城市组合数 2^(m-1)
        int n = 1 << (m - 1);
        int[][] dp = new int[m][n];
        // 第0列
        for (int k = 0; k < m; k++) {
            dp[k][0] = graph[k][0];
        }
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < m; i++) {
                dp[i][j] = Integer.MAX_VALUE / 2;
                if (contains(j, i)) {
                    continue;
                }
                //填充单元格
                for (int k = 0; k < m; k++) {

                }
            }
        }
        printDp(dp);
        return 0;
    }

    private static boolean contains(int j, int i) {
        return (j >> (i - 1) & 1) == 1;
    }

    private static int exclude(int j, int i) {
        return j ^ (1 << (i - 1));
    }

    private static void printDp(int[][] arr) {
        for (int[] its : arr) {
            for (int anInt : its) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }
}
